{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Path With Minimum Effort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #binary-search #matrix #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #二分查找 #矩阵 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumEffortPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小体力消耗路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你准备参加一场远足活动。给你一个二维 <code>rows x columns</code> 的地图 <code>heights</code> ，其中 <code>heights[row][col]</code> 表示格子 <code>(row, col)</code> 的高度。一开始你在最左上角的格子 <code>(0, 0)</code> ，且你希望去最右下角的格子 <code>(rows-1, columns-1)</code> （注意下标从 <strong>0</strong> 开始编号）。你每次可以往 <strong>上</strong>，<strong>下</strong>，<strong>左</strong>，<strong>右</strong> 四个方向之一移动，你想要找到耗费 <strong>体力</strong> 最小的一条路径。</p>\n",
    "\n",
    "<p>一条路径耗费的 <strong>体力值</strong> 是路径上相邻格子之间 <strong>高度差绝对值</strong> 的 <strong>最大值</strong> 决定的。</p>\n",
    "\n",
    "<p>请你返回从左上角走到右下角的最小<strong> 体力消耗值</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/25/ex1.png\" style=\"width: 300px; height: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>heights = [[1,2,2],[3,8,2],[5,3,5]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。\n",
    "这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/25/ex2.png\" style=\"width: 300px; height: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>heights = [[1,2,3],[3,8,4],[5,3,5]]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/25/ex3.png\" style=\"width: 300px; height: 300px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>上图所示路径不需要消耗任何体力。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>rows == heights.length</code></li>\n",
    "\t<li><code>columns == heights[i].length</code></li>\n",
    "\t<li><code>1 <= rows, columns <= 100</code></li>\n",
    "\t<li><code>1 <= heights[i][j] <= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [path-with-minimum-effort](https://leetcode.cn/problems/path-with-minimum-effort/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [path-with-minimum-effort](https://leetcode.cn/problems/path-with-minimum-effort/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,2],[3,8,2],[5,3,5]]', '[[1,2,3],[3,8,4],[5,3,5]]', '[[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\r\n",
    "        class State:\r\n",
    "            def __init__(self, x, y, effort_from_start):\r\n",
    "                self.x = x\r\n",
    "                self.y = y\r\n",
    "                self.effort_from_start = effort_from_start\r\n",
    "            def __lt__(self, other):\r\n",
    "                return self.effort_from_start < other.effort_from_start\r\n",
    "        m, n = len(heights), len(heights[0])\r\n",
    "\r\n",
    "        effort_to = [[float(\"inf\")] * n for _ in range(m)]\r\n",
    "        effort_to[0][0] = 0\r\n",
    "        pq = []\r\n",
    "        heapq.heappush(pq, State(0, 0, 0))\r\n",
    "        while pq:\r\n",
    "            cur = heapq.heappop(pq)\r\n",
    "            cur_x, cur_y, cur_effort_from_start = cur.x, cur.y, cur.effort_from_start\r\n",
    "            if cur_x == m-1 and cur_y == n-1:\r\n",
    "                return cur_effort_from_start\r\n",
    "            if cur_effort_from_start > effort_to[cur_x][cur_y]:\r\n",
    "                continue\r\n",
    "            for neighbor in self.adj(heights, cur_x, cur_y):\r\n",
    "                next_x, next_y = neighbor[0], neighbor[1]\r\n",
    "                effort_to_next = max(effort_to[cur_x][cur_y], \r\n",
    "                abs(heights[cur_x][cur_y] - heights[next_x][next_y])\r\n",
    "                )\r\n",
    "                if effort_to[next_x][next_y] > effort_to_next:\r\n",
    "                    effort_to[next_x][next_y] = effort_to_next\r\n",
    "                    heapq.heappush(pq, State(next_x, next_y, effort_to[next_x][next_y]))\r\n",
    "        return -1\r\n",
    "    \r\n",
    "    def adj(self, height, x, y):\r\n",
    "        m, n = len(height), len(height[0])\r\n",
    "        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\r\n",
    "        res = []\r\n",
    "        for d in dirs:\r\n",
    "            next_x, next_y = x+d[0], y+d[1]\r\n",
    "            if 0 <= next_x < m and 0 <= next_y < n:\r\n",
    "                res.append([next_x, next_y])\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        R = len(heights)\n",
    "        C = len(heights[0])\n",
    "        l = 0\n",
    "        r = 10**6+1\n",
    "        if R ==1 and C==1:\n",
    "            return 0\n",
    "        def check(T):\n",
    "            visited = [[False]*C for _ in range(R)]\n",
    "            Q = collections.deque([(0,0)])\n",
    "            while Q:\n",
    "                r,c = Q.popleft()\n",
    "                visited[r][c] = True\n",
    "                if r==R-1 and c == C-1:\n",
    "                    return True\n",
    "                for dr,dc in [[-1,0],[0,1],[1,0],[0,-1]]:\n",
    "                    nr = r+dr\n",
    "                    nc = c+dc\n",
    "                    if 0<=nr<R and 0<=nc<C and not visited[nr][nc] and abs(heights[r][c]-heights[nr][nc])<=T:\n",
    "                        visited[nr][nc]=True\n",
    "                        Q.append((nr,nc))\n",
    "            return False            \n",
    "                \n",
    "        while l<r:\n",
    "            mid = l+r >>1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:    \n",
    "                l = mid + 1\n",
    "        return l\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        # 动态规划，每个位置最小消耗值=max(前一个值消耗值， 前一个值到当前值需要消耗值)\n",
    "        row = len(heights)\n",
    "        col = len(heights[0])\n",
    "        if row == 1  and col == 1: return 0\n",
    "        power = [[float('inf')] * col for _ in range(row)]\n",
    "        power[0][0] = 0\n",
    "        queue = [(0, 0)]\n",
    "        result = float('inf')\n",
    "        # visited= set()\n",
    "        while queue:\n",
    "            i, j = queue.pop(0)\n",
    "            # visited.add((i, j))\n",
    "            for ii, jj in [(i-1,  j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                # print(str(i)+\"*\"+str(j), str(ii)+\"*\"+str(jj))\n",
    "                if 0 <= ii < row and 0 <= jj < col:\n",
    "                    consume = max(abs(heights[i][j] - heights[ii][jj]), power[i][j])\n",
    "                    if ii == row -1 and jj == col -1 and consume < result:\n",
    "                        result = consume\n",
    "                    elif consume < power[ii][jj]:  ## 因为当有更省力的路线出现，则加入队列，刷新该点之后的值；否则不刷新\n",
    "                        power[ii][jj] = consume\n",
    "                        # print(\"********\", (ii, jj))\n",
    "                        queue.append((ii, jj))\n",
    "            \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        # 动态规划，每个位置最小消耗值=max(前一个值消耗值， 前一个值到当前值需要消耗值)\n",
    "        row = len(heights)\n",
    "        col = len(heights[0])\n",
    "        if row == 1  and col == 1: return 0\n",
    "        power = [[float('inf')] * col for _ in range(row)]\n",
    "        power[0][0] = 0\n",
    "        queue = [(0, 0)]\n",
    "        result = float('inf')\n",
    "        while queue:\n",
    "            i, j = queue.pop(0)\n",
    "            for ii, jj in [(i-1,  j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                if 0 <= ii < row and 0 <= jj < col:\n",
    "                    consume = max(abs(heights[i][j] - heights[ii][jj]), power[i][j])\n",
    "                    if ii == row -1 and jj == col -1 and consume < result:\n",
    "                        result = consume\n",
    "                    elif consume < power[ii][jj]:\n",
    "                        power[ii][jj] = consume\n",
    "                        queue.append((ii, jj))\n",
    "            \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from itertools import chain\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        rows, cols = len(heights), len(heights[0])\n",
    "\n",
    "        def ok(m: int) -> bool:\n",
    "            vis = defaultdict(bool)\n",
    "            q = deque([[0, 0]])\n",
    "            vis[0] = True\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                if i == rows - 1 and j == cols - 1:\n",
    "                    return True\n",
    "                for di, dj in [[0, -1], [-1, 0], [0, 1], [1, 0]]:\n",
    "                    r, c = i + di, j + dj\n",
    "                    if 0 <= r < rows and 0 <= c < cols:\n",
    "                        k = r * 100 + c\n",
    "                        if (\n",
    "                            not vis[k]\n",
    "                            and abs(heights[r][c] - heights[i][j]) <= m\n",
    "                        ):\n",
    "                            vis[k] = True\n",
    "                            q.append([r, c])\n",
    "            return False\n",
    "\n",
    "        L, R = 0, max(chain(*heights)) - min(chain(*heights))\n",
    "        while L < R:\n",
    "            M = (L + R) >> 1\n",
    "            if ok(M):\n",
    "                R = M\n",
    "            else:\n",
    "                L = M + 1\n",
    "        return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import sys\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        m = len(heights)\n",
    "        n = len(heights[0])\n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        distance = [[sys.maxsize for _ in range(n)] for _ in range(m)]\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "        queue = [(0, 0, 0)]\n",
    "        heapq.heapify(queue)\n",
    "        while queue:\n",
    "            h, x, y = heapq.heappop(queue)\n",
    "\n",
    "            if visited[x][y]:\n",
    "                continue\n",
    "\n",
    "            visited[x][y] = True\n",
    "            distance[x][y] = h\n",
    "            for dx, dy in directions:\n",
    "                x1 = x + dx\n",
    "                y1 = y + dy\n",
    "                if 0 <= x1 < m and 0 <= y1 < n and not visited[x1][y1]:\n",
    "                    heapq.heappush(queue, (max(h, abs(heights[x][y] - heights[x1][y1])), x1, y1))\n",
    "\n",
    "        return distance[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minimumEffortPath(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        m = len(heights)\n",
    "        n = len(heights[0])\n",
    "\n",
    "        left = 0\n",
    "        right = 10**6\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            stack = []\n",
    "            seen = [[False] * n for _ in range(m)]\n",
    "            seen[0][0] = True\n",
    "            stack.append((0, 0))\n",
    "            while stack:\n",
    "                x, y = stack.pop(0)\n",
    "                for d in directions:\n",
    "                    xx = x + d[0]\n",
    "                    yy = y + d[1]\n",
    "                    if xx < 0 or xx >= m or yy < 0 or yy >= n or seen[xx][yy] or abs(heights[xx][yy] - heights[x][y]) > mid:\n",
    "                        continue\n",
    "                    stack.append((xx, yy))\n",
    "                    seen[xx][yy] = True\n",
    "            if seen[m-1][n-1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        dist = [ [ float('inf') for _ in range(n) ] for _ in range(m) ]\n",
    "        dist[0][0] = 0\n",
    "        q = [(0, 0)]\n",
    "        while q:\n",
    "            curx, cury = q.pop(0)\n",
    "            for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                nextx, nexty = curx + x, cury + y\n",
    "                if nextx < 0 or nexty < 0 or nextx >= m or nexty >= n: continue\n",
    "                d = max(dist[curx][cury], abs(heights[nextx][nexty] - heights[curx][cury]))\n",
    "                if d < dist[nextx][nexty] :\n",
    "                    dist[nextx][nexty]  = d\n",
    "                    q.append((nextx, nexty))\n",
    "        return dist[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "def neighbor(heights: List[List[int]], x: int, y: int) -> List[List[int]]:\n",
    "    m, n = len(heights), len(heights[0])\n",
    "    dirs = [[-1,0], [1,0], [0,-1], [0,1]]\n",
    "    res = []\n",
    "    for dir in dirs:\n",
    "        nextX, nextY = x + dir[0], y + dir[1]\n",
    "        if 0 <= nextX < m and 0 <= nextY < n:\n",
    "            res.append([nextX, nextY])\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        dist = [[float(\"inf\") for _ in range(n)] for _ in range(m)]\n",
    "        dist[0][0] = 0\n",
    "\n",
    "        pq = [(0,0,0)]\n",
    "        heapq.heapify(pq)\n",
    "        while pq:\n",
    "            x, y, cur_dist = heapq.heappop(pq)\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return cur_dist\n",
    "            if cur_dist > dist[x][y]:\n",
    "                continue\n",
    "\n",
    "            for nei in neighbor(heights, x, y):\n",
    "                x_next, y_next = nei[0], nei[1]\n",
    "                d = max(dist[x][y], abs(heights[x][y] - heights[x_next][y_next]))\n",
    "                if dist[x_next][y_next] > d:\n",
    "                    dist[x_next][y_next] = d\n",
    "                    heapq.heappush(pq, (x_next, y_next, d))\n",
    "            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        return self.dijkstra(0, 0, heights)\n",
    "\n",
    "    def adj(self, matrix, x, y):\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        neighbors = []\n",
    "        for _dir in self.dirs:\n",
    "            nx = x + _dir[0]\n",
    "            ny = y + _dir[1]\n",
    "            if nx >= m or nx < 0 or ny >= n or ny < 0:\n",
    "                continue\n",
    "            neighbors.append([nx, ny])\n",
    "        return neighbors\n",
    "\n",
    "    def dijkstra(self, startx, starty, heights):\n",
    "        efforTo = [[float('inf')]*len(heights[0]) for _ in range(len(heights))]\n",
    "        m = len(heights)\n",
    "        n = len(heights[0])\n",
    "        pq = []\n",
    "        efforTo[startx][starty] = 0\n",
    "        state = State(startx, starty, 0)\n",
    "        heapq.heappush(pq, (state.effortFromStart, state.x, state.y))\n",
    "        while list(pq) != []:\n",
    "            curEffortFromStart, curX, curY = heapq.heappop(pq)\n",
    "            if curX == m-1 and curY == n-1:\n",
    "                return curEffortFromStart\n",
    "            \n",
    "            if curEffortFromStart > efforTo[curX][curY]:\n",
    "                continue\n",
    "            for neighbor in self.adj(heights, curX, curY):          \n",
    "                nextX = neighbor[0]\n",
    "                nextY = neighbor[1]\n",
    "                effortToNext = max(efforTo[curX][curY], abs(heights[curX][curY] - heights[nextX][nextY]))\n",
    "\n",
    "                if efforTo[nextX][nextY] > effortToNext:\n",
    "                    efforTo[nextX][nextY] = effortToNext\n",
    "                    state = State(nextX, nextY, effortToNext)\n",
    "                    heapq.heappush(pq, (state.effortFromStart, state.x, state.y))\n",
    "        print(efforTo)\n",
    "        return -1\n",
    "\n",
    "class State:\n",
    "    def __init__(self, x, y, effortFromStart):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.effortFromStart = effortFromStart\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        # 构建优先级队列进行遍历\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        # 第一维表示距离，第二维表示i, 第三维表示j\n",
    "        que = [(0, 0, 0)]\n",
    "        while que:\n",
    "            dis, i, j = heapq.heappop(que)\n",
    "            # 已访问过的不再访问\n",
    "            if heights[i][j] < 0:\n",
    "                continue\n",
    "            if i == m - 1 and j == n - 1:\n",
    "                return dis\n",
    "            # 可以向上下左右四个方向遍历\n",
    "            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                x, y = i + dx, j + dy\n",
    "                # 越界或已访问过，则不再访问\n",
    "                if x < 0 or x >= m or y < 0 or y >= n or heights[x][y] < 0:\n",
    "                    continue\n",
    "                heapq.heappush(que, (max(dis, abs(heights[x][y] - heights[i][j])), x, y))\n",
    "            # 标记为已经访问过\n",
    "            heights[i][j] *= -1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        # 二分+bfs\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        inx = [0, 0, 1, -1]\n",
    "        iny = [1, -1, 0, 0]\n",
    "        def check(mid):\n",
    "            seen = set([(0, 0)])\n",
    "            que = deque([(0, 0)])\n",
    "            while que:\n",
    "                x, y = que.popleft()\n",
    "                for i in range(4):\n",
    "                    dx = x + inx[i]\n",
    "                    dy = y + iny[i]\n",
    "                    if dx >= 0 and dx < m and dy >= 0 and dy < n and abs(heights[dx][dy] - heights[x][y]) <=mid  and (dx, dy) not in seen:\n",
    "                        que.append((dx, dy))\n",
    "                        seen.add((dx, dy))\n",
    "            if (m-1, n-1) in seen:\n",
    "                return True\n",
    "            return False\n",
    "                    \n",
    "        l, r = 0, 10**6\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        rows = len(heights)\n",
    "        cols = len(heights[0])\n",
    "        dp = [[float('inf')] * cols for _ in range(rows)]  # dp[i][j]表示从开头走到(i,j)所消耗的最大体力\n",
    "        dp[0][0] = 0\n",
    "        dq =[(0, 0, 0)]  # 坐标+从开头走到(i,j)所消耗的最大体力\n",
    "        heapq.heapify(dq)\n",
    "        while dq:\n",
    "            cur_node = heapq.heappop(dq)\n",
    "            # print(cur_node)\n",
    "\n",
    "            if cur_node[0]==rows-1 and cur_node[1]==cols-1:\n",
    "                return cur_node[2]\n",
    "\n",
    "            # 相当于剪枝,因为同一个点会被走到多次，如果之前走到这个点的体力消耗比当前走到这个点的体力消耗要大，那说明之前走到这个点的路径不好，此时就直接放弃了\n",
    "            if cur_node[2] > dp[cur_node[0]][cur_node[1]]:\n",
    "                continue\n",
    "            # 看相邻点\n",
    "            for direction in [lambda x, y: (x - 1, y), lambda x, y: (x + 1, y), lambda x, y: (x, y - 1),\n",
    "                              lambda x, y: (x, y + 1)]:\n",
    "                next_node = direction(*cur_node[:2])\n",
    "                if 0 <= next_node[0] < rows and 0 <= next_node[1] < cols:\n",
    "                    next_node_high = max(dp[cur_node[0]][cur_node[1]],\n",
    "                                         abs(heights[next_node[0]][next_node[1]] - heights[cur_node[0]][cur_node[1]]))\n",
    "                    # 因为同一个点会被走到多次，所以这里有个判断，如果从start到这个点的体力消耗比之前其他路径走着这个点的体力消耗要小，说明此时的路径是个好路径，则更新体力消耗，并加入到未来要走的路中\n",
    "                    if next_node_high < dp[next_node[0]][next_node[1]] and next_node:\n",
    "                        dp[next_node[0]][next_node[1]] = next_node_high\n",
    "                        heapq.heappush(dq,(next_node[0], next_node[1], next_node_high))\n",
    "            # print(dq)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minimumEffortPath(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        m = len(heights)\n",
    "        n = len(heights[0])\n",
    "\n",
    "        left = 0\n",
    "        right = 10**6\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            stack = []\n",
    "            seen = [[False] * n for _ in range(m)]\n",
    "            seen[0][0] = True\n",
    "            stack.append((0, 0))\n",
    "            while stack:\n",
    "                x, y = stack.pop(0)\n",
    "                for d in directions:\n",
    "                    xx = x + d[0]\n",
    "                    yy = y + d[1]\n",
    "                    if xx < 0 or xx >= m or yy < 0 or yy >= n or seen[xx][yy] or abs(heights[xx][yy] - heights[x][y]) > mid:\n",
    "                        continue\n",
    "                    stack.append((xx, yy))\n",
    "                    seen[xx][yy] = True\n",
    "            if seen[m-1][n-1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        m = len(heights)\n",
    "        n = len(heights[0])\n",
    "\n",
    "        pq = []\n",
    "        di = [[1, 0], [0, 1], [-1, 0], [0, -1]]\n",
    "\n",
    "        distTo = [[float(\"inf\") for _ in range(n)] for _ in range(m)]\n",
    "        distTo[0][0] = 0\n",
    "\n",
    "        heapq.heappush(pq, [0, [0, 0]])\n",
    "\n",
    "        while pq:\n",
    "            distance, xy = heapq.heappop(pq)\n",
    "            x = xy[0]\n",
    "            y = xy[1]\n",
    "            if distance > distTo[x][y]:\n",
    "                continue\n",
    "\n",
    "            for d in di:\n",
    "                new_x = x + d[0]\n",
    "                new_y = y + d[1]\n",
    "                if new_x < m and new_y < n and new_x >= 0 and new_y >= 0:\n",
    "                    new_distance = max(abs(heights[new_x][new_y] - heights[x][y]), distTo[x][y])\n",
    "                    if new_distance < distTo[new_x][new_y]:\n",
    "                        distTo[new_x][new_y] = new_distance\n",
    "                        heapq.heappush(pq, [new_distance, [new_x, new_y]])\n",
    "                \n",
    "        return distTo[m-1][n-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        left, right, ans = 0, 10**6 - 1, 0\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            q = collections.deque([(0, 0)])\n",
    "            seen = {(0, 0)}\n",
    "            \n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                    if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in seen and abs(heights[x][y] - heights[nx][ny]) <= mid:\n",
    "                        q.append((nx, ny))\n",
    "                        seen.add((nx, ny))\n",
    "            \n",
    "            if (m - 1, n - 1) in seen:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        dist = [0] + [float(\"inf\")] * (m * n - 1)\n",
    "        seen = set()\n",
    "\n",
    "        while q:\n",
    "            d, x, y = heapq.heappop(q)\n",
    "            iden = x * n + y\n",
    "            if iden in seen:\n",
    "                continue\n",
    "            if (x, y) == (m - 1, n - 1):\n",
    "                break\n",
    "            \n",
    "            seen.add(iden)\n",
    "            for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                if 0 <= nx < m and 0 <= ny < n and max(d, abs(heights[x][y] - heights[nx][ny])) <= dist[nx * n + ny]:\n",
    "                    dist[nx * n + ny] = max(d, abs(heights[x][y] - heights[nx][ny]))\n",
    "                    heapq.heappush(q, (dist[nx * n + ny], nx, ny))\n",
    "        \n",
    "        return dist[m * n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        \"\"\" \"\"\" \n",
    "\n",
    "        direction = [(0,1), (0,-1), (1,0), (-1,0)] \n",
    "        m, n = len(heights), len(heights[0])\n",
    "\n",
    "        queue = [(0, 0, 0)]  # height / x / y \n",
    "        vis = set() \n",
    "\n",
    "        while queue:\n",
    "            curr_h, curr_i, curr_j = heapq.heappop(queue)\n",
    "            if (curr_i, curr_j) == (m-1, n-1):\n",
    "                return curr_h\n",
    "\n",
    "            if (curr_i, curr_j) in vis:\n",
    "                continue \n",
    "\n",
    "            vis.add((curr_i, curr_j))\n",
    "\n",
    "            for dx, dy in direction:\n",
    "                new_i, new_j = curr_i+dx, curr_j+dy \n",
    "                if (0 <= new_i < m) and (0 <= new_j < n) and (new_i, new_j) not in vis:\n",
    "                    new_h = max(curr_h, abs(heights[new_i][new_j] - heights[curr_i][curr_j]))\n",
    "                    heapq.heappush(queue, (new_h, new_i, new_j))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights):\n",
    "        row, col = len(heights), len(heights[0])\n",
    "        directions = [[-1,0],[0,-1], [1,0], [0,1]]\n",
    "        heap = []\n",
    "        visited = set()\n",
    "        heapq.heappush(heap, (0,0,0))\n",
    "        while heap:\n",
    "            cost, i, j = heapq.heappop(heap)\n",
    "            if (i, j) in visited: continue\n",
    "            visited.add((i, j))\n",
    "            if i == row - 1 and j == col - 1: \n",
    "                return cost\n",
    "            for d in directions:\n",
    "                new_i = i + d[0]\n",
    "                new_j = j + d[1]\n",
    "                if 0 <= new_i <= row - 1 and 0 <= new_j <= col - 1:\n",
    "                    new_cost = abs(heights[i][j] - heights[new_i][new_j])\n",
    "                    new_cost = max(cost, new_cost)\n",
    "                    heapq.heappush(heap, (new_cost, new_i, new_j))\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "\n",
    "        stack = [[0, 0, 0]]\n",
    "        heapq.heapify(stack)\n",
    "        visit = set()\n",
    "        while stack:\n",
    "            cost, i, j = heapq.heappop(stack)\n",
    "            if i == m - 1 and j == n - 1:\n",
    "                return cost\n",
    "            if (i, j) in visit:\n",
    "                continue\n",
    "            visit.add((i, j))\n",
    "            for x, y in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    cur = abs(heights[x][y] - heights[i][j])\n",
    "                    dis = cost if cost > cur else cur\n",
    "                    heapq.heappush(stack, [dis, x, y])\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind: \n",
    "    def __init__(self, n:int) :\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n \n",
    "        self.n = n \n",
    "\n",
    "        # \n",
    "        self.setCount = n \n",
    "\n",
    "    def findset(self, x: int) : \n",
    "        if self.parent[x] == x:\n",
    "            return x \n",
    "        \n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x, y): \n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "\n",
    "        if x == y : \n",
    "            return False \n",
    "        \n",
    "        if self.size[x] < self.size[y]: \n",
    "            x, y = y, x\n",
    "        \n",
    "        self.parent[y] = x \n",
    "        self.size[x] += self.size[y] \n",
    "\n",
    "        self.setCount -= 1 \n",
    "\n",
    "        return True \n",
    "    def connected(self, x, y):\n",
    "\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "\n",
    "        return x == y \n",
    "    \n",
    "    \n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        m,n = len(heights), len(heights[0])\n",
    "        edges = list()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                iden = i * n + j \n",
    "                if i > 0: \n",
    "                    edges.append((iden -n, iden, abs(heights[i][j] - heights[i-1][j])))\n",
    "                if j > 0:\n",
    "                    edges.append((iden - 1, iden, abs(heights[i][j]- heights[i][j-1])))\n",
    "        \n",
    "        edges.sort(key = lambda e:e[2])\n",
    "\n",
    "        uf = UnionFind(m * n)\n",
    "\n",
    "        ans = 0 \n",
    "\n",
    "        for x, y ,v in edges: \n",
    "            uf.unite(x,y)\n",
    "            if uf.connected(0, m * n - 1): \n",
    "                ans = v \n",
    "                break \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        edges = list()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                iden = i * n + j\n",
    "                if i > 0:\n",
    "                    edges.append((iden - n, iden, abs(heights[i][j] - heights[i - 1][j])))\n",
    "                if j > 0:\n",
    "                    edges.append((iden - 1, iden, abs(heights[i][j] - heights[i][j - 1])))\n",
    "        \n",
    "        edges.sort(key=lambda e: e[2])\n",
    "\n",
    "        uf = UnionFind(m * n)\n",
    "        ans = 0\n",
    "        for x, y, v in edges:\n",
    "            uf.unite(x, y)\n",
    "            if uf.connected(0, m * n - 1):\n",
    "                ans = v\n",
    "                break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        self.setCount = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        else:\n",
    "            return self.find(self.parent[x])\n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "    \n",
    "    def isConnected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        n, m = len(heights), len(heights[0])\n",
    "        edges = []\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                iden = i * m + j\n",
    "                if i > 0:\n",
    "                    edges.append((iden - m, iden, abs(heights[i][j] - heights[i - 1][j])))\n",
    "                if j > 0:\n",
    "                    edges.append((iden - 1, iden, abs(heights[i][j] - heights[i][j - 1])))\n",
    "        \n",
    "        edges.sort(key=lambda e: e[2])\n",
    "        s = UnionFind(m * n)\n",
    "        ans = 0\n",
    "        for x, y, w in edges:\n",
    "            s.union(x, y)\n",
    "            if s.isConnected(0, m * n - 1):\n",
    "                ans = w\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self, n):\n",
    "        self.parents = list(range(n))\n",
    "        self.sizes = [1] * n\n",
    "    \n",
    "    def find_set(self, x):\n",
    "        if self.parents[x] == x:\n",
    "            return x\n",
    "        return self.find_set(self.parents[x])\n",
    "\n",
    "    def union_set(self, x, y):\n",
    "        x = self.find_set(x)\n",
    "        y = self.find_set(y)\n",
    "        if self.sizes[x] > self.sizes[y]:\n",
    "            y, x = x, y\n",
    "        self.parents[x] = y\n",
    "        self.sizes[y] += self.sizes[x]\n",
    "\n",
    "    def is_connect(self, x, y):\n",
    "        x = self.find_set(x)\n",
    "        y = self.find_set(y)\n",
    "        return x == y\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        m = len(heights)\n",
    "        n = len(heights[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return 0\n",
    "        edges = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                idx = i * n + j\n",
    "                if i > 0:\n",
    "                    up_idx = (i-1)*n+j\n",
    "                    edges.append((idx, up_idx, abs(heights[i][j] - heights[i-1][j])))\n",
    "                if j > 0:\n",
    "                    left_idx = i * n + j - 1\n",
    "                    edges.append((idx, left_idx, abs(heights[i][j] - heights[i][j-1])))\n",
    "        union_set = UnionSet(m * n)\n",
    "        edges = sorted(edges, key=lambda x: x[-1])\n",
    "        for x, y, v in edges:\n",
    "            union_set.union_set(x, y)\n",
    "            if union_set.is_connect(0, m*n-1):\n",
    "                return v\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        n, m = len(heights), len(heights[0])\n",
    "        p = list(range(n*m))\n",
    "        def find(x):\n",
    "            if x != p[x]: p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        edges = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                idx = i * m + j\n",
    "                if i > 0:\n",
    "                    edges.append([idx-m, idx, abs(heights[i][j] - heights[i-1][j])])\n",
    "                if j > 0:\n",
    "                    edges.append([idx-1, idx, abs(heights[i][j] - heights[i][j-1])])\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "        ans = 0\n",
    "        for x, y, v in edges:\n",
    "            px, py = find(x), find(y)\n",
    "            p[px] = py\n",
    "            if find(0) == find(n * m - 1):\n",
    "                ans = v\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self, p, i):\n",
    "        cur = i\n",
    "        while p[cur]!=cur:\n",
    "            p[cur] = p[p[cur]]\n",
    "            cur = p[cur]\n",
    "        return p[cur]\n",
    "\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        m = len(heights)\n",
    "        n = len(heights[0])\n",
    "        p = [i for i in range(m*n)]\n",
    "        from queue import PriorityQueue\n",
    "        q = PriorityQueue()\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pos = i*n+j\n",
    "                if i+1<m:\n",
    "                    pos_i = (i+1)*n+j\n",
    "                    q.put((abs(heights[i][j]-heights[i+1][j]), (pos, pos_i,),))\n",
    "                if j+1<n:\n",
    "                    pos_j = i*n+j+1\n",
    "                    q.put((abs(heights[i][j]-heights[i][j+1]), (pos, pos_j,),))\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while self.find(p,0)!=self.find(p,m*n-1):\n",
    "            cost, (u, v) = q.get()\n",
    "            res = max(res, cost)\n",
    "            x,y = self.find(p, u),self.find(p,v)\n",
    "            if x<y: p[y] = x\n",
    "            else: p[x] = y\n",
    "        \n",
    "        return res\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        rows = len(heights)\n",
    "        columns = len(heights[0])\n",
    "        n = rows * columns\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for r in range(rows):\n",
    "            for c in range(columns):\n",
    "                start = r * columns + c\n",
    "                if r > 0:\n",
    "                    end = (r - 1) * columns + c\n",
    "                    weight = abs(heights[r][c] - heights[r - 1][c])\n",
    "                    graph[start].append((end, weight))\n",
    "                    graph[end].append((start, weight))\n",
    "                if c > 0:\n",
    "                    end = r * columns + c - 1\n",
    "                    weight = abs(heights[r][c] - heights[r][c - 1])\n",
    "                    graph[start].append((end, weight))\n",
    "                    graph[end].append((start, weight))\n",
    "        \n",
    "        distances = [sys.maxsize] * n\n",
    "        distances[0] = 0\n",
    "\n",
    "        nodes = [(0, 0)]\n",
    "        while nodes:\n",
    "            distance, current = heapq.heappop(nodes)\n",
    "            if current == n - 1:\n",
    "                return distance\n",
    "            if distance == distances[current]:\n",
    "                for neighbor, weight in graph[current]:\n",
    "                    distance = max(distances[current], weight)\n",
    "                    if distance < distances[neighbor]:\n",
    "                        distances[neighbor] = distance\n",
    "                        heapq.heappush(nodes, (distance, neighbor))\n",
    "        return distances[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        class UnionFind:\n",
    "            def __init__(self):\n",
    "                self.parents=dict()\n",
    "            \n",
    "            def find(self, node):\n",
    "                if node not in self.parents:\n",
    "                    self.parents[node] = node\n",
    "                \n",
    "                while self.parents[node] != node:\n",
    "                    node = self.parents[node]\n",
    "                \n",
    "                return node\n",
    "            \n",
    "            def union(self, node1, node2):\n",
    "                parent1 = self.find(node1)\n",
    "                parent2 = self.find(node2)\n",
    "                self.parents[parent1] = parent2\n",
    "\n",
    "        row, col = len(heights), len(heights[0])\n",
    "\n",
    "        uf = UnionFind()\n",
    "        if uf.find((0,0)) == uf.find((row-1, col-1)):\n",
    "            return 0\n",
    "\n",
    "        edges = []\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if j + 1 < col:\n",
    "                    weight = abs(heights[i][j] - heights[i][j+1])\n",
    "                    edges.append((weight, (i,j), (i, j+1)))\n",
    "                if i + 1 < row:\n",
    "                    weight = abs(heights[i][j] - heights[i+1][j])\n",
    "                    edges.append((weight, (i,j), (i+1, j)))\n",
    "\n",
    "        edges = sorted(edges, key=lambda edge: edge[0])\n",
    "\n",
    "        for weight, node1, node2 in edges:\n",
    "            uf.union(node1, node2)\n",
    "\n",
    "            if uf.find((0,0)) == uf.find((row-1, col-1)):\n",
    "                return weight\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "d={1:(0,1),2:(0,-1),3:(1,0),4:(-1,0)}\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        # if row==1 and col==1:\n",
    "        #     return 0\n",
    "        row=len(heights)\n",
    "        col=len(heights[0])\n",
    "        left,right=-1,10**6\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            print(mid)\n",
    "            visited=[[False]*col for _ in range(row)]\n",
    "            if self.dfs(0,0,visited,mid,heights):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid\n",
    "        return right\n",
    "\n",
    "    def dfs(self,x,y,visited,target,h):\n",
    "        if x==len(h)-1 and y==len(h[0])-1:\n",
    "            return True\n",
    "        if not visited[x][y]:\n",
    "            for i in range(1,5):\n",
    "                newx=x+d[i][0]\n",
    "                newy=y+d[i][1]\n",
    "                if 0<=newx<len(h) and 0<=newy<len(h[0]) and not visited[newx][newy] and abs(h[x][y]-h[newx][newy])<=target:\n",
    "                    visited[x][y]=True\n",
    "                    if self.dfs(newx,newy,visited,target,h):\n",
    "                        return True\n",
    "        return False\n",
    "\n",
    "    \n",
    "        \n",
    "\n",
    "    \n",
    "        \n",
    "       \n",
    "\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        edges = []\n",
    "        nl = len(heights[0])\n",
    "        for i in range(0, len(heights)):\n",
    "            for j in range(0, len(heights[0])):\n",
    "                try:\n",
    "                    edges.append([i*nl+j, i*nl+j+1, abs(heights[i][j+1]-heights[i][j])])\n",
    "                except:\n",
    "                    pass\n",
    "                try:\n",
    "                    edges.append([i*nl+j, i*nl+j+nl, abs(heights[i+1][j]-heights[i][j])])\n",
    "                except:\n",
    "                    pass\n",
    "        tar = len(heights)*nl-1\n",
    "        fa = [i for i in range(0, tar+1)]\n",
    "        def find(node):\n",
    "            if node == fa[node]:\n",
    "                return fa[node]\n",
    "            else:\n",
    "                return find(fa[node])\n",
    "        edges.sort(key=lambda x:x[2])\n",
    "        ans = 0\n",
    "        for u, v, dis in edges:\n",
    "            if find(0) == find(tar):\n",
    "                break\n",
    "            if find(u) == find(v):\n",
    "                continue\n",
    "            fa[find(v)] = find(u)\n",
    "            ans = max(ans, dis)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        directions = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        m = len(heights)\n",
    "        n = len(heights[0])\n",
    "        ans = 0\n",
    "        path_min = heights[0][0]\n",
    "        dct = defaultdict(dict)\n",
    "        for i in range(m):#准备数据\n",
    "            for j in range(n):\n",
    "                for d,e in directions:\n",
    "                    if 0<=i+d<=m-1 and 0<=j+e<=n-1:\n",
    "                        u = i*n + j\n",
    "                        v = (i+d)*n + j + e\n",
    "                        dct[u][v] = abs(heights[i][j] - heights[i+d][j+e])\n",
    "        #print(dct)\n",
    "        #print(l)\n",
    "        dist = [inf] * (m*n)\n",
    "        dist[0] = 0\n",
    "        stack = [[0,0]]\n",
    "        while stack:\n",
    "            d,i = heappop(stack) #d的含义变了：\n",
    "            if d > dist[i]:\n",
    "                continue\n",
    "            for j in dct[i]:\n",
    "                if max(dct[i][j],d)<dist[j]:\n",
    "                    dist[j] = max(dct[i][j],d)\n",
    "                    heappush(stack,[dist[j],j])\n",
    "        #print(dist)\n",
    "        return dist[m*n-1]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    2. connect start cell and end cell\n",
    "    3. the max gap between two cell should be smallest\n",
    "    4. start from smallest effort edge, connecting group, and see if start and end cells are included \n",
    "    5. flatten the matrix\n",
    "    6. create a list id, index = cell position, value = final root\n",
    "    7. create a list graph, element: [cell1, cell2, height_gap]\n",
    "    '''\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        row = len(heights)\n",
    "        col = len(heights[0])\n",
    "\n",
    "        id = [i for i in range((row-1)*col + col)]\n",
    "        edges = dict()\n",
    "        dirs = [[0,1], [1, 0]] # right and down\n",
    "\n",
    "        for x in range(row):\n",
    "            for y in range(col):\n",
    "                for d in dirs:\n",
    "                    new_x = x + d[0]\n",
    "                    new_y = y + d[1]\n",
    "                    if 0 <= new_x < row and 0 <= new_y < col:\n",
    "                        edges[(x*col + y, new_x*col + new_y)] = abs(heights[x][y] - heights[new_x][new_y])\n",
    "\n",
    "        sorted_edges = sorted(edges.items(), key=lambda item: item[1]) # sort by value desc\n",
    "        print(sorted_edges)\n",
    "        max_effort = 0\n",
    "\n",
    "        for edge in sorted_edges:\n",
    "            p = self.find_root(id, edge[0][0])\n",
    "            q = self.find_root(id, edge[0][1])\n",
    "            id[q] = p # connect cells\n",
    "            if self.find_root(id, 0 * col + 0) == self.find_root(id, (row - 1)* col + col - 1):\n",
    "                return edges[edge[0]]\n",
    "            \n",
    "        return 0\n",
    "    \n",
    "    def find_root(self, id, i):\n",
    "        while i != id[i]:\n",
    "            id[i] = id[id[i]]\n",
    "            i = id[i]\n",
    "        return i \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        dxdy = [[-1,0], [1,0],[0,1],[0,-1]]\n",
    "        m = len(heights)\n",
    "        n = len(heights[0])\n",
    "        \n",
    "\n",
    "        def dfs(x, y, k):\n",
    "            # print(x,y,k)\n",
    "            vis[x][y] = True\n",
    "            if x == m-1 and y == n-1:\n",
    "                return True\n",
    "            for dx,dy in dxdy:\n",
    "                px, py = x + dx, y + dy\n",
    "                if px >= m or px < 0  or py >= n or py < 0 or abs(heights[px][py] - heights[x][y]) > k or vis[px][py]:\n",
    "                    continue\n",
    "                if dfs(px, py, k):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        l, r= 0, 1000000\n",
    "        while l < r:\n",
    "            vis = [[False] * n for _ in range(m)]\n",
    "            mid = (l + r) // 2\n",
    "            is_reach = dfs(0, 0, mid)\n",
    "            if is_reach:    ## 说明可以达到，那么就应该将代价减小\n",
    "                r = mid\n",
    "            else:   ## 无法在mid消耗内达到，就应该将代价增大\n",
    "                l = mid + 1\n",
    "\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        tp=[[[] for _ in range(len(heights[0]))] for _ in range(len(heights))]\n",
    "        for c in range(len(heights[0])):\n",
    "            for r in range(len(heights)-1):\n",
    "                d=abs(heights[r][c]-heights[r+1][c])\n",
    "                tp[r][c]+=[((r+1,c),d)]\n",
    "                tp[r+1][c]+=[((r,c),d)]\n",
    "        for r in range(len(heights)):\n",
    "            for c in range(len(heights[0])-1):\n",
    "                d=abs(heights[r][c]-heights[r][c+1])\n",
    "                tp[r][c]+=[((r,c+1),d)]\n",
    "                tp[r][c+1]+=[((r,c),d)]\n",
    "        rr=[[-1]*len(heights[0]) for _ in range(len(heights))]\n",
    "        dq=[(0,(0,0))]\n",
    "        while dq:\n",
    "            (m,(r,c))=heapq.heappop(dq)\n",
    "            if rr[r][c]!=-1:continue\n",
    "            rr[r][c]=m\n",
    "            for np in tp[r][c]:\n",
    "                (nr,nc)=np[0]\n",
    "                if rr[nr][nc]!=-1:continue\n",
    "                heapq.heappush(dq,(max(m,np[1]),np[0]))\n",
    "        return rr[-1][-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
